import sys

class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        if k >= len(prices)//2:
            maxProfit = 0
            lastPrice = sys.maxsize
            for price in prices:
                maxProfit += max(0, price-lastPrice)
                lastPrice = price
            return maxProfit

        dp = [[0 for _ in range(len(prices))] for _ in range(k+1)]
        for time in range(1, k+1):
            maxProfit = -prices[0]
            for i in range(1, len(prices)):
                dp[time][i] = max(dp[time][i-1], maxProfit + prices[i])
                maxProfit = max(maxProfit, dp[time-1][i-1]-prices[i])
        return dp[-1][-1]



